package 滑动窗口;

/**
 * https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/
 * 将 x 减为 0 的最小操作数
 */
public class likou1658 {

    // 正难则反，该求中间连续区间和 = sums - x 的最大区间
    // 时间：O（N）+ O（N）
    // 空间 ：O（1）
    public int minOperations(int[] nums, int x) {
        // 暴力枚举-——> 滑动窗口
        // 1. left = 0,right = 0;
        int left = 0, right = 0;
        int sum = 0; // 区间和
        int sums = 0;  // 总和
        // int len = 0; // 最大取0 不影响结果
        int len = -1; // 用 0 就不可以. -1 就可以. 有可能 0 会干扰结果. len 有可能为 0. len == 0 的时候, 结果就是全部长度.
        // 求和
        for(int a : nums) sums += a;

        int target = sums - x; // 目标值
        if(target < 0) return -1;

        for(;right < nums.length; right++) {
            // 2.进窗口, 加完之后判断
            sum += nums[right];
            // 3.判断
            while(sum > target) {
                sum -= nums[left];
                left++; // 出窗口
            }
            // 出循环说明 sum < target 或者 = target
            if(sum == target) {
                len = Math.max(len, right - left + 1); // 更新结果
            }
        }
        if(len == -1) return -1;
        else return nums.length - len;
        // return len == 0 ? -1 : nums.length - len;
    }

}
